package problems;

import java.util.HashMap;
import java.util.Map;

/**
 * See http://mathworld.wolfram.com/PartitionFunctionP.html
 * @author László van den Hoek
 *
 */
public class Euler076 extends AbstractEuler {

	//cache
	private Map<Long, Long> partitionings = new HashMap<Long, Long>();
	{
		partitionings.put(0L, 1L);
		partitionings.put(1L, 1L);
	}
	
	@Override
	public Number calculate() {
		return numberOfPartitionings(100) - 1; //minus one because we can not include the whole number
	}
	
	public void testNUpTo5() {
		assertEquals(0, numberOfPartitionings(-1));
		assertEquals(1, numberOfPartitionings(0));
		assertEquals(1, numberOfPartitionings(1));
		assertEquals(2, numberOfPartitionings(2));
		assertEquals(3, numberOfPartitionings(3));
		assertEquals(5, numberOfPartitionings(4));
		assertEquals(7, numberOfPartitionings(5));
	}
	
	public void testN300() {
		assertEquals(9253082936723602L, numberOfPartitionings(300));
	}

	@Override
	protected Number getCorrectAnswer() {
		return 190569291L;
	}
	
	private long numberOfPartitionings(long n) {
		if (n < 0) {
			//you can't partition a negative number into positive ones
			return 0;
		} else if (partitionings.containsKey(Long.valueOf(n))) {
			//retrieve from cache
			return partitionings.get(Long.valueOf(n));
		} else {
			//apply Skiena's recurrence equation based on Euler's generating function
			//P(n)=sum_(k=1)^n(-1)^(k+1)[P(n-1/2k(3k-1))+P(n-1/2k(3k+1))] 
			long answer = 0;
			for (long k = 1; k <= n; k++) {
				long nextTerm =
					numberOfPartitionings(n - ((k * (3*k - 1)) / 2)) +
					numberOfPartitionings(n - ((k * (3*k + 1)) / 2));
				if (k % 2 == 0) {
					answer -= nextTerm;
				} else {
					answer += nextTerm;
				}
			}

			//cache the result
			partitionings.put(Long.valueOf(n), answer);
			
			return answer;
		}
	}

}
